package com.arelikebrothers.demo.algorithm.basic.analysis;

/**
 * Created by lennon on 12/06/2017.
 */
public class MaxContiguousSubsequenceSum {

    /**
     * O(n^2)
     *
     * @param a
     * @return
     */
    public static int maxSubSum(int[] a) {
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            int thisSum = 0;
            for (int j = i; j < a.length; j++) {
                thisSum += a[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }

        return maxSum;
    }

    /**
     * O(NlogN)
     *
     * @param a
     * @return
     */
    public static int maxSubSum2(int[] a) {
        return maxSubSumRec(a, 0, a.length - 1);
    }

    /**
     * 使用分治法计算最大子序列和
     *
     * @param a
     * @param left
     * @param right
     * @return
     */
    public static int maxSubSumRec(int[] a, int left, int right) {
        if (left == right) {
            if (a[left] > 0) {
                return a[left];
            }
            return 0;
        }

        int center = (left + right) / 2;

        int maxLeftSum = maxSubSumRec(a, left, center);
        int maxRightSum = maxSubSumRec(a, center + 1, right);

        // 计算左边界最大值
        int maxLeftBorderSum = 0;
        int leftBorderSum = 0;
        for (int i = center; i >= left; i--) {
            leftBorderSum += a[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBorderSum;
            }
        }

        // 计算右边界最大值
        int maxRightBorderSum = 0;
        int rightBorderSum = 0;
        for (int i = center + 1; i <= right; i++) {
            rightBorderSum += a[i];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }

        int maxBorderSum = maxLeftBorderSum + maxRightBorderSum;

        int max = Math.max(Math.max(maxLeftSum, maxRightSum), maxBorderSum);


        return max;
    }

    /**
     * O(N)
     *
     * @param a
     * @return
     */
    public static int maxSubSum3(int[] a) {
        int thisSum = 0;
        int maxSum = 0;

        int start = 0, end = 0;

        for (int i = 0; i < a.length; i++) {
            thisSum += a[i];

            if (thisSum > maxSum) {
                maxSum = thisSum;
                end = i;
            } else if (thisSum < 0) {
                start = i + 1;
                thisSum = 0;
            }
        }
        System.out.println("i = " + start + ", j=" + end);

        return maxSum;
    }


    public static void main(String[] args) {
        int[] a = {-2, -1, -4, 13, -5, -2 , 8};

//        int maxSubSum = maxSubSum(a);
//        System.out.println(maxSubSum);

//        int maxSubSum = maxSubSum2(a);
//        System.out.println(maxSubSum);

        int maxSubSum = maxSubSum3(a);
        System.out.println(maxSubSum);

    }
}
